UVa/12317 - Document Compression/ana.cpp

   1 // Code written by Ana Echavarría
   2 using namespace std;
   3 #include <iostream>
   4 #include <vector>
   5 #include <queue>
   6
   7 // Maximum base size is 2^16 - 1
   8 const int maxN = 1 << 16;
   9 int length [maxN];
  10
  11 int main(){
  12         int nBases, nDocs;
  13         while(cin >> nBases >> nDocs){
  14                 if  (nBases == 0 and nDocs == 0) break;
  15                 //Initialize length
  16                 for (int i = 0; i < maxN; i++) length[i] = -1;
  17                 // Read the bases
  18                 vector <int> bases(nBases, 0);
  19                 for (int b = 0; b < nBases; b++){
  20                         int k; cin >> k;
  21                         while(k--){
  22                                 int num; cin >> num;
  23                                 bases[b] |= 1 << (num-1);
  24                         }
  25                 }
  26                 // Read the documents
  27                 vector <int> docs(nDocs, 0);
  28                 for (int d = 0; d < nDocs; d++){
  29                         int k; cin >> k;
  30                         while(k--){
  31                                 int num; cin >> num;
  32                                 docs[d] |= 1 << (num-1);
  33                         }
  34                 }
  35                 // Start BFS
  36                 queue <int> q;
  37                 q.push(0);
  38                 length[0] = 0;
  39                 while(q.size() > 0){
  40                         int curr = q.front();
  41                         q.pop();
  42                         for (int i = 0; i < bases.size(); i++){
  43                                 // Build next document
  44                                 int next = curr | bases[i];
  45                                 // Check if it has not been visited yet
  46                                 if (length[next] >= 0) continue;
  47                                 length[next] = length[curr] + 1;
  48                                 q.push(next);
  49                         }
  50                 }
  51                 // Print answers
  52                 for (int d = 0; d < docs.size(); d++){
  53                         int document = docs[d];
  54                         if (length[document] >= 0) cout << length[document];
  55                         else cout << 0;
  56                         if (d < docs.size() - 1) cout << " ";
  57                         else cout << endl;
  58                 }
  59
  60         }
  61
  62     return 0;
  63 }